package com.sheng.leetcode.year2023.month02.day03;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/02/03
 * <p>
 * 1145. 二叉树着色游戏<p>
 * <p>
 * 有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，<p>
 * 树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。<p>
 * 最开始时：<p>
 * 「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）；<p>
 * 「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x。<p>
 * 「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色。<p>
 * 之后两位玩家轮流进行操作，「一号」玩家先手。每一回合，玩家选择一个被他染过色的节点，<p>
 * 将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色（「一号」玩家染红色，「二号」玩家染蓝色）。<p>
 * 如果（且仅在此种情况下）当前玩家无法找到这样的节点来染色时，其回合就会被跳过。<p>
 * 若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。<p>
 * 现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个 y 值可以确保你赢得这场游戏，则返回 true ；若无法获胜，就请返回 false 。<p>
 * <p>
 * 示例 1 ：<p>
 * 输入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3<p>
 * 输出：true<p>
 * 解释：第二个玩家可以选择值为 2 的节点。<p>
 * <p>
 * 示例 2 ：<p>
 * 输入：root = [1,2,3], n = 3, x = 1<p>
 * 输出：false<p>
 * <p>
 * 提示：<p>
 * 树中节点数目为 n<p>
 * 1 <= x <= n <= 100<p>
 * n 是奇数<p>
 * 1 <= Node.val <= n<p>
 * 树中所有值 互不相同<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/binary-tree-coloring-game">1145. 二叉树着色游戏</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1145 {

    @Test
    public void test01() {
        TreeNode left = new TreeNode(2);
        TreeNode left01 = new TreeNode(4);
        left01.left = new TreeNode(8);
        left01.right = new TreeNode(9);
        TreeNode right01 = new TreeNode(5);
        right01.left = new TreeNode(10);
        right01.right = new TreeNode(11);
        left.left = left01;
        left.right = right01;
        TreeNode right = new TreeNode(3);
        right.left = new TreeNode(6);
        right.right = new TreeNode(7);
        TreeNode root = new TreeNode(1);
        root.left = left;
        root.right = right;
        int n = 11, x = 3;

//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(3);
//        int n = 3, x = 1;
        System.out.println(new Solution().btreeGameWinningMove(root, n, x));
    }
}

class Solution {

    int xLeft, xRight;

    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        // 两位玩家，玩家一先手选额 x 节点，判断时候存在一个节点 y 可以确保玩家二赢
        // 题意转换，在 x 的左子树/右子树/父节点中，是否存在其中一个大于另外两个之和
        // 即求出 x 的左右节点的大小，xLeft 和 xRight，父节点大小为总长度 n - 1 - xLeft - xRight，总大小减去 x 左右节点和 x 本身大小
        dfs(root, x);
        return Math.max(xLeft, Math.max(xRight, n - xLeft - xRight - 1)) * 2 > n;
    }

    public int dfs(TreeNode root, int x) {
        if (root == null) {
            return 0;
        }
        // 获取左右子节点的长度
        int left = dfs(root.left, x);
        int right = dfs(root.right, x);
        if (root.val == x) {
            xLeft = left;
            xRight = right;
        }
        return left + right + 1;
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
